28 找出字符串中第一个匹配项的下标

https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnr003/

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

cost: 25m43s

KMP 的更快的原因就是子串在匹配的时候，如果发现不匹配，直接跳到子串的某个下标继续匹配，而不是从头开始匹配。如果当前已经匹配的子串后缀和子串前缀相同，那么就可以从子串前缀不相等的部分开始匹配。

那么这个索引表该如何计算呢？设 f(i) 为下标 i 的对应索引，那么 f(i) = f(i-1) + 1。
已知 f(i-1) 为 j, 那么：
- 如果 s[i] == s[j+1]，那么 f(i) = j + 1
- 如果 s[i] != s[j+1]，那么 f(i) <= j。此时应该从 [0, j] 之间寻找 f(i) 的值，进一步如果发现 s[i] != s[j]，那么应该去 [0, f(i-2)] 中寻找 f(i) 的值。

class Solution {
public:
    int strStr(string haystack, string needle) {
        vector<int> memo(needle.size());
        for (int i = 1, j = 0; i < needle.size(); i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = memo[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            memo[i] = j;
        }
        for (int i = 0, j = 0; i < haystack.size();) {
            if (needle[j] == haystack[i]) {
                i++;
                j++;
                if (needle.size() == j) {
                    return i - j;
                }
                continue;
            }
            if (j == 0) {
                i++;
                continue;
            }
            j = memo[j - 1];
        }
        return -1;
    }
};

• 时间复杂度：O(n1 + n2)
• 空间复杂度：O(n2)